#include <cstdio>
#include "regalloc.h"
#include "lir.h"

using namespace std;

class X86Encoder;

X86Encoder RegAllocNode::encoder;
int RegAllocOperand::nextId = 0;

int RegAlloc::totalRegs;

RegAllocNode* RegAlloc::createNode(BasicBlock* bb)
{
    RegAllocNode *node = new RegAllocNode(bb,RegAlloc::getTotalRegs());
    return node;
}

bool RegAlloc::replaceDst(Lir *lir,int spilledId,int tempId)
{
    switch(lir->type){
    case ADD:
    case SUB:
    case MUL:
    case DIV:
    case MOV:
    case SPILL_LOAD:
    case LOADCONST:
        RegOperand *oper = dynamic_cast<RegOperand*>(lir->dst);
        assert(oper && "the lir'dst isn't a RegOperand");

        if(spilledId == *oper){
            *oper = tempId;
            return true;
        }
        break;
    }

    // PushOp,PopOp,CondGotoOp. these don't have dst
    // SpillStore'dst can be replaced
    return false;
}

bool RegAlloc::replaceArgs(Lir *lir,int spilledId,int tempId)
{
    bool ret = false;
    RegOperand *reg;

    switch(lir->type){
    case MOV:
    case SPILL_STORE:
    case PUSH:
    case POP:
    case JMP:
    case JNE:
        if(lir->arg1->isRegOperand()){
            reg = dynamic_cast<RegOperand*>(lir->arg1);
            if(spilledId == *reg){
                *reg = tempId;
                ret = true;
            }
        }
        break;
    case ADD:
    case SUB:
    case MUL:
    case DIV:
        if(lir->arg1->isRegOperand()){
            reg = dynamic_cast<RegOperand*>(lir->arg1);
            if(spilledId == *reg){
                *reg = tempId;
                ret = true;
            }
        }
        if(lir->arg2->isRegOperand()){
            reg = dynamic_cast<RegOperand*>(lir->arg2);
            if(spilledId == *reg){
                *reg = tempId;
                ret = true;
            }
        }
        break;
    }

    // SpillLoad,LoadConstOp. their args can't be replaced
    return false;
}

/// get the lir defs, or -1 if none is defined
int RegAlloc::getDefs(Lir *lir)
{
    int def = -1;

    switch(lir->type){
    case ADD:
    case SUB:
    case MUL:
    case DIV:
    case MOV:
    case SPILL_LOAD:
    case LOADCONST:
        assert(lir->dst->isRegOperand() && "the dest operand isn't RegOperand");
        RegOperand *reg = dynamic_cast<RegOperand*>(lir->dst);
        def = *reg;
        break;
    }

    return def;
}

/// get the lir uses, the used virtual register in uses,reture the size
int RegAlloc::getUses(Lir *lir,int uses[])
{
    int size = 0;
    RegOperand *reg;

    switch(lir->type){
    case MOV:
    case SPILL_STORE:
    case PUSH:
    case POP:
    case JMP:
    case JNE:
        if(lir->arg1->isRegOperand()){
            reg = dynamic_cast<RegOperand*>(lir->arg1);
            uses[0] = *reg;
            size = 1;
        }
        break;
    case ADD:
    case SUB:
    case MUL:
    case DIV:
        if(lir->arg1->isRegOperand()){
            reg = dynamic_cast<RegOperand*>(lir->arg1);
            uses[size++] = *reg;
        }
        if(lir->arg2->isRegOperand()){
            reg = dynamic_cast<RegOperand*>(lir->arg2);
            uses[size++] = *reg;
        }
        break;
    }

    return size;
}

void RegAlloc::scanBlocks()
{
    CFG::iterator it;
    RegAllocNode::lir_iterator lit;
    RegOperand *reg;

    for(it = cfg->begin();it != cfg->end();it++){
        BasicBlock *bb = *it;
        RegAllocNode *node = getOrCreateNode(bb);
        //log<<"[regalloc]scaning block"<<bb->getDfsNo()<<endl;

        for(lit = node->lirs.begin();lit != node->lirs.end();lit++){
            Lir *lir = *lit;

            if(lir->dst && lir->dst->isRegOperand()){
                reg = dynamic_cast<RegOperand*>(lir->dst);
                node->define(*reg);
            }
            if(lir->arg1 && lir->arg1->isRegOperand()){
                reg = dynamic_cast<RegOperand*>(lir->arg1);
                node->use(*reg);
            }
            if(lir->arg2 && lir->arg2->isRegOperand()){
                reg = dynamic_cast<RegOperand*>(lir->arg2);
                node->use(*reg);
            }
        }
    }
}

void RegAlloc::analyzeLiveOut()
{
    CFG::dfs_reverse_iterator it;
    list<BasicBlock*> workList;

    scanBlocks();

    remove_copy_if(cfg->dfsRbegin(),cfg->dfsRend(),
                   back_inserter(workList),
                   bind2nd(equal_to<BasicBlock*>(),cfg->getStartBlock()));
    // exclude start and end block
    workList.remove(const_cast<BasicBlock*>(cfg->getEndBlock()));

    log<<"total: "<<totalRegs<<endl;
    while(!workList.empty()){
        BasicBlock *bb = workList.front();
        workList.pop_front();

        dyn_bitset tmpSet(totalRegs,false);
        RegAllocNode *node = getOrCreateNode(bb);
        //log<<"[regalloc]buildLiveness blocks: "<<bb->getDfsNo()<<endl;

        for(BasicBlock::succ_iterator succ_it = bb->getSuccBegin();
            succ_it != bb->getSuccEnd();succ_it++){
            BasicBlock *sbb = *succ_it;
            RegAllocNode *snode = getOrCreateNode(sbb);
            bitsetOr(tmpSet,*snode->liveIn);
        }

        // now tmpSet is liveOut
        bitsetAndNot(tmpSet,*node->killed);
        bitsetOr(tmpSet,*node->gen);

        if(tmpSet != *node->liveIn){
            log<<"[regalloc]changed"<<endl;
            *node->liveIn = tmpSet;
            if(!count(workList.begin(),workList.end(),bb)){
                workList.push_back(bb);
            }
        }
    }

    // calculate the liveOut
    for(CFG::iterator bit = cfg->begin();bit != cfg->end();bit++){
        BasicBlock *bb = *bit;
        RegAllocNode *node = getOrCreateNode(bb);

        for(BasicBlock::succ_iterator succ_it = bb->getSuccBegin();
            succ_it != bb->getSuccEnd();succ_it++){
            BasicBlock *sbb = *succ_it;
            RegAllocNode *snode = getOrCreateNode(sbb);

            bitsetOr(*node->liveOut,*snode->liveIn);
        }
    }

}

void RegAlloc::addEdge(dyn_bitset& adjs,int regNum)
{
    for(int i = 0;i < adjs.size();i++){
        if(adjs[i]){
            initial[regNum]->addAdj(i);
            initial[i]->addAdj(regNum);
        }
    }
}

void RegAlloc::addEdge(set<int>& adjs,int regNum)
{
    for(set<int>::iterator it = adjs.begin();it != adjs.end();it++){
        initial[regNum]->addAdj(*it);
        initial[*it]->addAdj(regNum);
    }
}

void RegAlloc::addWorklist(RegAllocOperand *operand)
{
    set<Lir*> activeAndWorklist = setUnion(activeMoves,worklistMoves);
    // TODO: consider precolor case
    if(!operand->isMoveRelated(activeAndWorklist) && operand->degree < K){
        freezeWorklist.remove(operand);
        simplifyWorklist.push_back(operand);
    }
}

void RegAlloc::enableMoves(set<int>& regs)
{
    set<int>::iterator it;
    set<Lir*>::iterator mit;
    set<Lir*> activeAndWorklist = setUnion(activeMoves,worklistMoves);

    log<<"enableMoves"<<endl;
    for(it = regs.begin();it != regs.end();it++){
        set<Lir*> moves = initial[*it]->nodeMoves(activeAndWorklist);
        for(mit = moves.begin();mit != moves.end();mit++){
            if(activeMoves.find(*mit) != activeMoves.end()){
                activeMoves.erase(*mit);
                worklistMoves.insert(*mit);
            }
        }
    }
}

void RegAlloc::decrementDegree(RegAllocOperand *operand)
{
    int degree = operand->degree--;

    if(degree == K){
        set<Lir*> activeAndWorklist = setUnion(activeMoves,worklistMoves);
        set<int> adjs = operand->getAdjlist();
        adjs.insert(operand->getId());
        enableMoves(adjs);
        spillWorklist.remove(operand);

        if(operand->isMoveRelated(activeAndWorklist)){
            freezeWorklist.push_back(operand);
        } else {
            simplifyWorklist.push_back(operand);
        }
    }
}

void RegAlloc::combine(RegAllocOperand *u,RegAllocOperand *v)
{
    RegOperand *regSrc,*regDst;

    if(find(freezeWorklist.begin(),freezeWorklist.end(),v) !=
       freezeWorklist.end()){
        freezeWorklist.remove(v);
    } else {
        spillWorklist.remove(v);
    }

    coalescedNodes.push_back(v);

    // moves v's related moves into u if possible
    for(set<Lir*>::iterator it = v->moveList.begin();it != v->moveList.end();it++){
        Lir *lir = *it;
        if(worklistMoves.find(lir) != worklistMoves.end() ||
           activeMoves.find(lir) != activeMoves.end()){
            // the op should not invole u if it can be added to u's moveList. ? not quite understand
            regSrc = dynamic_cast<RegOperand*>(lir->arg1);
            regDst = dynamic_cast<RegOperand*>(lir->dst);
            assert(regSrc && regDst && "the dst and src of move lir should be RegOperand");

            if(getAlias(initial[*regDst]) != u &&
               getAlias(initial[*regSrc]) != u){
                u->addMove(lir);
            }
        }
    }

    v->alias = u;
    set<int> adjs = v->getAdjlist();
    addEdge(adjs,u->getId());
    for(set<int>::iterator it = adjs.begin();it != adjs.end();it++){
        decrementDegree(initial[*it]);
    }

    if(u->degree >= K &&
       find(freezeWorklist.begin(),freezeWorklist.end(),u) !=
       freezeWorklist.end()){
        freezeWorklist.remove(u);
        spillWorklist.push_back(u);
    }
}

RegAllocOperand* RegAlloc::getAlias(RegAllocOperand* operand)
{
    if(find(coalescedNodes.begin(),coalescedNodes.end(),operand) !=
       coalescedNodes.end()){
        return getAlias(operand->alias);
    } else {
        return operand;
    }
}


void RegAlloc::freezeMoves(RegAllocOperand *operand)
{
    Lir *lir;
    RegOperand *regSrc,*regDst;
    int assocRegNum;
    set<Lir*>::iterator movit;
    set<Lir*> activeAndWorklist = setUnion(activeAndWorklist,worklistMoves);
    set<Lir*> moves = operand->nodeMoves(activeAndWorklist);

    for(movit = moves.begin();movit != moves.end();movit++){
        lir = *movit;
        regSrc = dynamic_cast<RegOperand*>(lir->arg1);
        regDst = dynamic_cast<RegOperand*>(lir->dst);
        assert(regSrc && regDst && "Invalid move lir");

        if(operand->getId() == *regSrc){ // move is ( operand->id <- assocOperand )
            assocRegNum = *regDst;
        } else {
            assocRegNum = *regSrc;
            assert(operand->getId() == *regDst &&
                   "the moveInstruction doesn't involve the operand");
        }

        if(activeMoves.find(lir) != activeMoves.end()){
            activeMoves.erase(lir);
        } else {
            assert(worklistMoves.find(lir) != worklistMoves.end() &&
                   "the moveInstruction is not in worklistMoves when *freezeMoves*");
            worklistMoves.erase(lir);
        }

        frozenMoves.insert(lir);

        RegAllocOperand *assocOperand = initial[assocRegNum];
        set<Lir*> assocMoves = assocOperand->nodeMoves(activeAndWorklist);
        if(assocMoves.empty() && assocOperand->degree < K){
            freezeWorklist.remove(assocOperand);
            simplifyWorklist.push_back(assocOperand);
        }
    }
}

bool RegAlloc::isSafeCoalesce(RegAllocOperand *v,RegAllocOperand *u)
{
    bool isSafe = true;
#if 0                        // TODO: consider precolor
    if(u->in(precolor)){
        set<int> adjs = v->getAdjlist();
        for(set<int>::iterator it = adjs.begin();it != adjs.end();it++){
            RegAllocOperand *t = initial[*it];
            if(t->degree < K || t->in(precolor) ||t->interfere(u)){
                continue;
            } else {
                isSafe = false;
                break;
            }
        }
    }

    if(isSafe){
        return true;
    }

    assert(!u->in(precolor) && "RegAllocOperand isn't in precolor ? ");
#endif
    set<int> uvadjs = setUnion(u->getAdjlist(),v->getAdjlist());
    int k = 0;
    for(set<int>::iterator it = uvadjs.begin();it != uvadjs.end();it++){
        if(initial[*it]->degree >= K){
            k++;
        }
    }

    return k < K;
}

/// reset the worklists and lirs before each iteration
void RegAlloc::initialize()
{
    initial.clear();
    simplifyWorklist.clear();
    freezeWorklist.clear();
    spillWorklist.clear();
    spilledNodes.clear();
    coalescedNodes.clear();
    coloredNodes.clear();
    selectStack.clear();
    coalescedMoves.clear();
    constrainedMoves.clear();
    frozenMoves.clear();
    worklistMoves.clear();
    activeMoves.clear();

    collectOperands();

    // tell RegAllocOperand the next id for newly made one
    RegAllocOperand::setTotalReg(totalRegs);
}

void RegAlloc::addOperand(int regNum)
{
    if(initial.find(regNum) == initial.end()){
        // this virtual register hasn't been added yet
        initial[regNum] = new RegAllocOperand(regNum);
        totalRegs++;
    }
}

void RegAlloc::collectOperands()
{
    CFG::iterator it;
    RegOperand *reg;
    totalRegs = 0;

    for(it = cfg->begin();it != cfg->end();it++){
        BasicBlock *bb = *it;
        RegAllocNode *node = getOrCreateNode(bb);
        for(RegAllocNode::lir_iterator lit = node->lirs.begin();lit != node->lirs.end();lit++){
            Lir *lir = *lit;

            if(lir->dst && lir->dst->isRegOperand()){
                reg = dynamic_cast<RegOperand*>(lir->dst);
                addOperand(*reg);
            }
            if(lir->arg1 && lir->arg1->isRegOperand()){
                reg = dynamic_cast<RegOperand*>(lir->arg1);
                addOperand(*reg);
            }
            if(lir->arg2 && lir->arg2->isRegOperand()){
                reg = dynamic_cast<RegOperand*>(lir->arg2);
                addOperand(*reg);
            }
        }
    }

    // resize the live set for each node as the virtual regiters
    // number may change, i.e. spilled registers require rewriting
    // as the cfg->begin()/end() doesn't contain all the blocks(begin and end)
    // blocks, so use dfsBegin/dfsEnd instead

    //for( it = cfg->begin();it != cfg->end();it++){
    for(CFG::dfs_iterator it = cfg->dfsBegin();it != cfg->dfsEnd();it++){

        RegAllocNode *node = getOrCreateNode(*it);
        node->reset(totalRegs);
    }
}

/// build the interference graph
void RegAlloc::build()
{
    int def;
    int use;

    for(CFG::iterator bit = cfg->begin();bit != cfg->end();bit++){
        BasicBlock *bb = *bit;
        RegAllocNode *node = getOrCreateNode(bb);
        dyn_bitset& liveOut = *node->liveOut;

        for(RegAllocNode::lir_reverse_iterator rit = node->lirs.rbegin();rit != node->lirs.rend();rit++){
            Lir *lir = *rit;
            RegOperand *reg;

            if(lir->type == MOV){
                // TODO: the dst may not be a RegOperand
                if(lir->dst->isRegOperand()){
                    reg = dynamic_cast<RegOperand*>(lir->dst);
                    def = *reg;
                }
                if(lir->arg1->isRegOperand()){
                    reg = dynamic_cast<RegOperand*>(lir->arg1);
                    use = *reg;
                    // live = live - use
                    liveOut[use] = false;
                }

                RegAllocOperand* operand = initial[def];
                assert(operand && "the operand doesn't exist");
                assert(operand->getId() == def && "regalloc operand id is wrong");
                operand->addMove(lir);
                operand = initial[use];
                assert(operand->getId() == use && "regalloc operand id is wrong");
                operand->addMove(lir);

                worklistMoves.insert(lir);
            }

            int size;
            int uses[4];
            def = getDefs(lir);
            size = getUses(lir,uses);

            if(def != -1){
                // live = live   V   def
                liveOut[def] = true;
                addEdge(liveOut,def);

                // live = use   V   (live - def)
                liveOut[def] = false;
            }

            for(int i = 0;i < size;i++){
                liveOut[uses[i]] = true;
            }
        }
    }
}

void RegAlloc::makeWorklist()
{
    map<int,RegAllocOperand*>::iterator it;
    set<Lir*> activeAndWorklist = setUnion(activeMoves,worklistMoves);

    for(it = initial.begin();it != initial.end();it++){
        RegAllocOperand* operand = it->second;
        if(operand->degree >= K){
            spillWorklist.push_back(operand);
        } else if(operand->isMoveRelated(activeAndWorklist)) {
            freezeWorklist.push_back(operand);
        } else {
            simplifyWorklist.push_back(operand);
        }
    }
}

void RegAlloc::simplify()
{
    RegAllocOperand *operand = simplifyWorklist.front();
    simplifyWorklist.pop_front();
    selectStack.push_back(operand);

    set<int> adjs = operand->getAdjlist();
    set<int>::iterator it;

    for(it = adjs.begin();it != adjs.end();it++){
        decrementDegree(initial[*it]);
    }
}

void RegAlloc::coalesce()
{
    set<Lir*>::iterator it = worklistMoves.begin();
    assert(it != worklistMoves.end() && "the worklistMoves is empty when coalesce");
    Lir *lir = *it;
    RegOperand *regSrc,*regDst;
    assert(lir->type == MOV && "isn't move lir?");
    worklistMoves.erase(it);

    regSrc = dynamic_cast<RegOperand*>(lir->arg1);
    regDst = dynamic_cast<RegOperand*>(lir->dst);

    RegAllocOperand *src = getAlias(initial[*regSrc]);
    RegAllocOperand *dst = getAlias(initial[*regDst]);
    // TODO: consider precolor

    if(src == dst){
        coalescedMoves.insert(lir);
        addWorklist(src);
    } else if (src->interfere(dst)){ // TODO: consider precolor
        constrainedMoves.insert(lir);
        addWorklist(src);
        addWorklist(dst);
    } else if (isSafeCoalesce(src,dst)) {              // TODO: consider precolor
        coalescedMoves.insert(lir);
        combine(src,dst);
        addWorklist(src);
    } else {
        activeMoves.insert(lir);
    }
}

void RegAlloc::freeze()
{
    RegAllocOperand *operand = freezeWorklist.front();
    freezeWorklist.pop_front();
    simplifyWorklist.push_back(operand);

    freezeMoves(operand);
}

void RegAlloc::selectSpill()
{
    RegAllocOperand *operand = spillWorklist.front();
    spillWorklist.pop_front();
    simplifyWorklist.push_back(operand);

    freezeMoves(operand);
}

void RegAlloc::assignColors()
{
    while(!selectStack.empty()){
        RegAllocOperand *operand = selectStack.front();
        selectStack.pop_front();

        unsigned int okColors = availRegMask;
        set<int> adjs = operand->getAdjlist();

        for(set<int>::iterator it = adjs.begin();it != adjs.end();it++){
            RegAllocOperand *alias = getAlias(initial[*it]);
            // TODO: consider precolor
            if(find(coloredNodes.begin(),coloredNodes.end(),alias) != coloredNodes.end()){
                assert(alias->realRegister != -1 &&
                       "the realRegister isn't assigned but in coloredNodes");
                okColors &= ~(1 << alias->realRegister);
            }
        }

        //log<<"okColors[before assign]: "<<std::hex<<okColors<<std::dec<<"   ";
        assert(okColors >= 0 && "okColors isn't correct");
        if(!okColors){
            log<<"spill operand: "<<operand->getId()<<endl;
            spilledNodes.push_back(operand);
        } else {
            // assign any color to it
            int i;
            for(i = 0;i < K ;i++){
                if(okColors & 1<<i){ // 1 << 0 == 1
                    log<<operand->getId()<<" assigned register "<<i<<endl;
                    operand->realRegister = i;
                    break;
                }
            }
            assert(i < K && "the assigned color is out of range");
            coloredNodes.push_back(operand);
        }
    }

    for(list<RegAllocOperand*>::iterator it = coalescedNodes.begin();it != coalescedNodes.end();it++){
        RegAllocOperand *alias = getAlias(*it);
        (*it)->realRegister = alias->realRegister;
    }
}

void RegAlloc::rewriteProgram()
{
    RegOperand *regSrc,*regDst;
    int nspill = spilledNodes.size();

    log<<"total spilled nodes are "<<nspill<<endl;
    assert(nspill > 0 && "rewriting the program when no spill !");
    int index = 0;
    for(int i = 0;i < nspill;i++){
        int offset = index * 4;     // assume the register is 32-bit
        bool referenced = false;
        RegAllocOperand *temp = 0;
        RegAllocOperand *operand = spilledNodes.front();
        spilledNodes.pop_front();

        // check all lirs of this cfg that reference the spilled operand,
        // replace it with new Temp Operand and corresponding *store* and *load* lir
        for(CFG::iterator it = cfg->begin();it != cfg->end();it++){
            RegAllocNode *node = getOrCreateNode(*it);
            for(RegAllocNode::lir_iterator lit = node->lirs.begin();lit != node->lirs.end();lit++){
                Lir *lir = *lit;

                if(operand->referencedBy(lir)){
                    referenced = true;
                    if(!temp){
                        temp = RegAllocOperand::make();
                    }

                    if(lir->type == MOV){
                        // remove redundant moves
                        regSrc = dynamic_cast<RegOperand*>(lir->arg1);
                        regDst = dynamic_cast<RegOperand*>(lir->dst);
                        if((int)(*regSrc) == (int)(*regDst)){  // dst == src == spill
                            log<<"remove redundat move"<<endl;
                            node->lirs.remove(lir);
                            continue;
                        }

                        if(operand->getId() == *regDst){
                            // replace "spill = src" to SpillStore
                            //log<<"replace "<<mop->dst<<" = "<<mop->src<<endl;
                            *lit = new Lir(SPILL_STORE,new ConstantOperand<int>(offset),regSrc);
                        } else {
                            // replace "dst = spill" to SpillLoad
                            // log<<"replace "<<mop->dst<<" = "<<mop->src<<endl;
                            assert(operand->getId() == *regSrc && "spilled register not referenced");
                            *lit = new Lir(SPILL_LOAD,regDst,new ConstantOperand<int>(offset));
                        }

                        continue;
                    }

                    // replace the lir's dst with the created temp register
                    if(replaceDst(lir,operand->getId(),temp->getId())){
                        // insert the store-to-mem lir after this one
                        LirQueue::iterator lit1 = lit;
                        lit1++;
                        node->lirs.insert(lit1,new Lir(SPILL_STORE,new ConstantOperand<int>(offset),new RegOperand(temp->getId())));
                    }
                    // replace the opcode's args with the created temp register
                    if(replaceArgs(lir,operand->getId(),temp->getId())){
                        // insert the load-to-mem opcode before each use
                        node->lirs.insert(lit,new Lir(SPILL_LOAD,new RegOperand(temp->getId()),new ConstantOperand<int>(offset)));
                    }
                }
            }

            if(referenced){
                index++;
            }
        }
    }
}

/// remove the moves that src == dst
void RegAlloc::removeRedundantMoves()
{
    RegOperand *regSrc,*regDst;
    for(CFG::iterator it = cfg->begin();it != cfg->end();it++){
        RegAllocNode *node = getOrCreateNode(*it);
        for(RegAllocNode::lir_iterator lit = node->lirs.begin();lit != node->lirs.end();){
            Lir *lir = *lit;
            bool removed = false;

            // NOTE: use postincrement as erase may invalidate iterator
            if(lir->type == MOV){
                regSrc = dynamic_cast<RegOperand*>(lir->arg1);
                regDst = dynamic_cast<RegOperand*>(lir->dst);
                if(initial[*regDst]->realRegister ==
                   initial[*regSrc]->realRegister){
                    node->lirs.erase(lit++);
                    removed = true;
                }
            }

            if(!removed){
                lit++;
            }
        }
    }
}

LirQueue& RegAlloc::getLirsFor(BasicBlock *bb)
{
    // TODO: add the getNode interface
    RegAllocNode *node = getOrCreateNode(bb);
    return node->lirs;
}

/// the main rounting
void RegAlloc::allocateRegister()
{
    for(;;){
        log<<"[regalloc]======== ITERATION STARTS ========"<<endl;
        initialize();
        analyzeLiveOut();
        build();
        makeWorklist();
        for(;;){
            if(!simplifyWorklist.empty()){
                log<<"simplify  ";
                simplify();
            } else if (!worklistMoves.empty()) {
                log<<"coalesce  ";
                coalesce();
            } else if (!freezeWorklist.empty()) {
                log<<"freeze  ";
                freeze();
            } else if (!spillWorklist.empty()) {
                log<<"selectSpill  ";
                selectSpill();
            } else {
                break;
            }
        }
        assignColors();
        if(spilledNodes.empty()){
            log<<"[regalloc] successfully assign colors"<<endl;
            removeRedundantMoves();
            break;
        }
        rewriteProgram();
        //printLirs();
    }
    printLirs();
    assignRealRegister();
}

void RegAlloc::printBlocks()
{
    CFG::dfs_iterator it;

    for(it = cfg->dfsBegin();it != cfg->dfsEnd();it++){
        BasicBlock *bb = *it;
        RegAllocNode *node = getOrCreateNode(bb);
        log<<"Block"<<bb->getDfsNo()<<":liveIn: ";
        if(log.getDebug()){
            copy(node->liveIn->rbegin(),node->liveIn->rend(),ostream_iterator<bool>(log.getStream()));
        }
        log<<endl;
        log<<"Block"<<bb->getDfsNo()<<":liveOut: ";
        if(log.getDebug()){
            copy(node->liveOut->rbegin(),node->liveOut->rend(),ostream_iterator<bool>(log.getStream()));
        }
        log<<endl;
    }
}

void RegAlloc::printOperands()
{
    for(map<int,RegAllocOperand*>::iterator it = initial.begin();it != initial.end();it++){
        int regNum = it->first;
        int regNum1;
        if(initial.find(regNum) == initial.end()){
            regNum1 = -1;
        } else {
            regNum1 = initial[regNum]->realRegister;
        }

        log<<"reg["<<regNum<<"] --> "<<regNum1<<endl;
    }
}

void RegAlloc::printLirs()
{
    log<<"[realloc] printLirs"<<endl;

#define chg(x...) assert(lir->x->isRegOperand() && "not RegOperand");   \
    x = *(dynamic_cast<RegOperand*>(lir->x));   \

    int dst,arg1,arg2;

    for(CFG::iterator it = cfg->begin();it != cfg->end();it++){
        RegAllocNode *node = getOrCreateNode(*it);
        for(RegAllocNode::lir_iterator lit = node->lirs.begin();lit != node->lirs.end();lit++){
            Lir *lir = *lit;

            switch(lir->type){
            case ADD:
                chg(dst);
                chg(arg1);
                chg(arg2);
                log<<"Add "<<dst<<":"<<arg1<<":"<<arg2<<endl;
                break;
            case SUB:
                chg(dst);
                chg(arg1);
                chg(arg2);
                log<<"Sub "<<dst<<":"<<arg1<<":"<<arg2<<endl;
                break;
            case MUL:
                chg(dst);
                chg(arg1);
                chg(arg2);
                log<<"Mul "<<dst<<":"<<arg1<<":"<<arg2<<endl;
                break;
            case DIV:
                chg(dst);
                chg(arg1);
                chg(arg2);
                log<<"Div "<<dst<<":"<<arg1<<":"<<arg2<<endl;
                break;
            case MOV:
                chg(dst);
                chg(arg1);
                log<<"Mov "<<dst<<":"<<arg1<<endl;
                break;
            case SPILL_LOAD:
                chg(dst);
                log<<"SpillLoad "<<dst<<endl;
                break;
            case SPILL_STORE:
                chg(arg1);
                log<<"SpillStore "<<" <= "<<dst<<endl;
                break;
            case PUSH:
                chg(dst);
                log<<"Push "<<dst<<endl;
                break;
            case POP:
                chg(dst);
                log<<"Pop "<<dst<<endl;
                break;
            case LOADCONST:
                chg(dst);
                log<<"LOADCONST "<<dst<<endl;
                break;
                /*case JMP:
                chg(arg1);
                log<<"JMP "<<endl;
                break;
                case JNE:
                chg(dst);
                log<<"JNE "<<dst<<endl;
                break;*/
            case ORri:
                chg(dst);
                log<<"ORri "<<dst<<endl;
                break;
            }
        }
    }
#undef chg
}

void RegAlloc::printAllocatedCode()
{
    log<<"[realloc] printAllocatedCode"<<endl;

//#define chg(x...) x = initial[*(dynamic_cast<RegOperand*>(lir->x))]->realRegister;
#define chg(x...) x = *(dynamic_cast<RegOperand*>(lir->x));

    int dst,arg1,arg2;

    for(CFG::iterator it = cfg->begin();it != cfg->end();it++){
        RegAllocNode *node = getOrCreateNode(*it);
        for(RegAllocNode::lir_iterator lit = node->lirs.begin();lit != node->lirs.end();lit++){
            Lir *lir = *lit;
            switch(lir->type){
            case ADD:
                chg(dst);
                chg(arg1);
                chg(arg2);
                log<<"Add "<<dst<<":"<<arg1<<":"<<arg2<<endl;
                break;
            case SUB:
                chg(dst);
                chg(arg1);
                chg(arg2);
                log<<"Sub "<<dst<<":"<<arg1<<":"<<arg2<<endl;
                break;
            case MUL:
                chg(dst);
                chg(arg1);
                chg(arg2);
                log<<"Mul "<<dst<<":"<<arg1<<":"<<arg2<<endl;
                break;
            case DIV:
                chg(dst);
                chg(arg1);
                chg(arg2);
                log<<"Div "<<dst<<":"<<arg1<<":"<<arg2<<endl;
                break;
            case MOV:
                chg(dst);
                chg(arg1);
                log<<"Mov "<<dst<<":"<<arg1<<endl;
                break;
            case SPILL_LOAD:
                chg(dst);
                log<<"SpillLoad "<<dst<<endl;
                break;
            case SPILL_STORE:
                chg(arg1);
                log<<"SpillStore "<<" <= "<<arg1<<endl;
                break;
            case PUSH:
                chg(dst);
                log<<"Push "<<dst<<endl;
                break;
            case POP:
                chg(dst);
                log<<"Pop "<<dst<<endl;
                break;
            case LOADCONST:
                chg(dst);
                log<<"LOADCONST "<<dst<<endl;
                break;
            case JMP:
                log<<"JMP "<<endl;
                break;
            case JNE:
                log<<"JNE "<<endl;
                break;
            case ORri:
                chg(dst);
                log<<"ORri "<<dst<<endl;
                break;
            }
        }
    }
    log<<"coalescedMoves"<<coalescedMoves.size()<<endl;
};
#undef chg

/// assgin real register to the lir operands to replace the virtual registers
void RegAlloc::assignRealRegister()
{
    RegOperand *reg;
    set<RegOperand*> assigned;

//#define chg(x...) x = initial[*(dynamic_cast<RegOperand*>(lir->x))]->realRegister;
#define assgin_real(x...) assert(lir->x->isRegOperand() && "assignRealRegister: not RegOperand"); \
    reg = dynamic_cast<RegOperand*>(lir->x);                            \
    if(assigned.count(reg) == 0){                                       \
        assigned.insert(reg);                                           \
        *reg=initial[*reg]->realRegister;                               \
    }

    //return;

    for(CFG::iterator it = cfg->begin();it != cfg->end();it++){
        RegAllocNode *node = getOrCreateNode(*it);
        for(RegAllocNode::lir_iterator lit = node->lirs.begin();lit != node->lirs.end();lit++){
            Lir *lir = *lit;

            switch(lir->type){
            case ADD:
            case SUB:
            case MUL:
            case DIV:
                assgin_real(dst);
                assgin_real(arg1);
                assgin_real(arg2);
                break;
            case MOV:
                assgin_real(dst);
                assgin_real(arg1);
                break;
            case SPILL_LOAD:
                assgin_real(dst);
                break;
            case SPILL_STORE:
                assgin_real(arg1);
                break;
            case PUSH:
                assgin_real(dst);
                break;
            case POP:
                assgin_real(dst);
                break;
            case LOADCONST:
                assgin_real(dst);
                break;
            case JMP:
            case JNE:
                break;
            case ORri:
                assgin_real(dst);
                break;
            }
        }
    }
#undef assgin_real
}


void RegAnalysis(CFG *cfg)
{
    RegAlloc *ra = new RegAlloc(cfg);
//    ra.analyzeLiveOut();
    ra->allocateRegister();
//    ra.printBlocks();
//    ra->printLirs();
//    ra->printOperands();
    ra->printAllocatedCode();

}




